CBC Casper: Finality inspector
Reference: The Inspector – hackingresearch
Algorithm
Calculate level 0 messages from MessageDAG
level 0 message := a message after which the validator never changes its mind.
Recalculate levels without validators that have no level 1 message.
level 1 message := a message for which a large number $ q of latest messages in its justification are level 0.
https://gyazo.com/05b2b47f38aadfb157b1a672041fb107
In this case, validator 4 has no level 1 message, so recalculate levels without validator 4.
https://gyazo.com/d45fe18e137913a238730f2d42e0d6ed
This is the result.
Complexity
Definitions
$ E:=The number of edges in MessageDAG.
$ V:=The number of vertices in MessageDAG.
Time Complexity
$ O(VE)
Recalculations happens worst $ V times and the time complexity of recalculation is $ O(E).
Space Complexity
$ O(V+E)
Threshold
n/2 + x vs n/2 - x
k: Level (k + 1 is the round)
e: # of equivocation from this level or round
table: a
k e Scores seen by k + 1 Scores seen by k + 2
1 x n/2 : n/2 n/2 : n/2 - x
2 x/2 n/2 - x/2 : n/2 - x/2 n/2 - x/2 : n/2 - x
3 x/4 n/2 - 3x/4 : n/2 - 3x/4 n/2 - 3x/4: n/2 - x
k 2^(-k)x n/2 - {1 - 2^(- k + 1)}x
This is the optimal attack by the adversary
The goal is to create unobservable equivocations from the highest layer